package com.fanco.learn_datastruct_leetcode.leetcode;
/**
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 示例：
 * 输入：{-2,1,-3,4,-1,2,1,-5,4}
 * 输出：6
 * @author Fanco
 */
public class Day25 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int [] array = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(solution.maxSubArray(array));
    }
    private static class Solution {
        public int maxSubArray(int[] nums) {
            int pre = 0; int maxAns = nums[0];
            for (int i = 0; i < nums.length; i++) {
                pre = Math.max(pre + nums[i], nums[i]);
                maxAns = Math.max(maxAns, pre);
            }
            return maxAns;
        }
    }
}
